﻿// 0820train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

/*
 输入 m 和 n 两个数，m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。
 棋盘中存在数字和"."两种字符，如果是数字表示该位置是一匹马，
 如果是"."表示该位置为空的，棋盘内的数字表示为该马能走的最大步数。
例如棋盘内某个位置一个数字为 k，表示该马只能移动 0~k 步的距离。
棋盘内的马移动类似于中国象棋中的马移动，先在水平或者垂直方向上移动一格，然后再将其移动到对角线位置。
棋盘内的马可以移动到同一个位置，同一个位置可以有多匹马。
请问能否将棋盘上所有的马移动到同一个位置，若可以请输出移动的最小步数。若不可以输出 0

输入描述
输入m 和 n 两个数，m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据

输出描述
能否将棋盘上所有的马移动到同一个位置，若可以请输入移动的最小步数。若不可以输出 0

输入
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .
输出
17
 */

class Solution01
{
public:
    int curr_target = 0, curr_step_limit = 0, curr_step_count = 0;
    //先处理方向矩阵
    vector<vector<int>>getDirGrid()
    {
        vector<vector<int>>dir_grid;
        vector<vector<int>>simple_grid = { {-1,0},{1,0},{0,-1},{0,1} };
        vector<vector<int>>trangle_grid = { {-1,-1},{-1,1},{1,-1},{1,1} };

        for (auto&simple_dir:simple_grid)
        {
	        for (auto&trangle_dir:trangle_grid)
	        {
                vector<int>new_dir(2);
                new_dir[0] = simple_dir[0] + trangle_dir[0];
                new_dir[1] = simple_dir[1] + trangle_dir[1];

                if (new_dir[0]!=0&&new_dir[1]!=0)
                {
                    dir_grid.push_back(new_dir);
                }
	        }
        }
        return dir_grid;
    }

    void bfs(vector<vector<int>>&checked, queue<pair<int,int>>&bfs_queue)
    {
        while (!bfs_queue.empty())
        {
            curr_step_count++;

            if (curr_step_count > curr_step_limit)
            {
                break;
            }

            //层叠遍历
            int q_size = bfs_queue.size();
            for (int i=0; i<q_size; i++)
            {
                pair<int, int>top_node = bfs_queue.front();
                bfs_queue.pop();
                //方向矩阵遍历
                for (auto&dir_vec:DirectionGrid)
                {
                    int curr_r = top_node.first + dir_vec[0];
                    int curr_c = top_node.second + dir_vec[1];

                    bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                    bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                    if (is_curr_r && is_curr_c)
                    {
                        bool is_visited = checked[curr_r][curr_c] > -1;
                        if (!is_visited)
                        {
                            bfs_queue.push(make_pair(curr_r, curr_c));
                            checked[curr_r][curr_c] = curr_step_count;
                        }

                    }

                }
                //for q_size
            }
            //while (!bfs_queue.empty())
        }

        //for (auto&min_vec:checked)
        //{
	       // for (auto&num:min_vec)
	       // {
        //        cout << num << ' ';
	       // }
        //    cout << '\n';
        //}
	    
    }

    bool updateStatistic(vector<vector<int>>&checked)
    {
        bool result = false;
        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                if (curr_target==1)
                {
                    statistic_grid[r][c] = checked[r][c];
                    continue;
                }

                if (statistic_grid[r][c]>-1&&checked[r][c]>-1)
                {
                    result = true;
                    statistic_grid[r][c] += checked[r][c];
                }

	        }
        }

        //cout << "checked" << endl;
        //for (auto&min_vec:checked)
        //{
	       // for (auto&num:min_vec)
	       // {
        //        cout << num << ' ';
	       // }
        //    cout << '\n';
        //}
        //cout << "statistic" << endl;
        //for (auto& min_vec : statistic_grid)
        //{
        //    for (auto& num : min_vec)
        //    {
        //        cout << num << ' ';
        //    }
        //    cout << '\n';
        //}
        return result;
	    
    }

    void solve01(vector<vector<int>>&grid)
    {
        //初始化变量
        row_size = grid.size();
        col_size = grid[0].size();
        DirectionGrid = getDirGrid();
        vector<vector<int>>statistic(row_size, vector<int>(col_size, -1));
        statistic_grid = statistic;
        
        //双重遍历，记录curr_target, curr_step_limit
        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                int first_val = grid[r][c];
                
                if (first_val>-1)
                {
                    //每一轮重新生成checked，bfs_queue
                    queue<pair<int, int>>bfs_queue;
                    vector<int>checked_status(col_size, -1);
                    vector<vector<int>>checked(row_size, checked_status);

                    checked[r][c] = 0; //起点位置
                    bfs_queue.push(make_pair(r, c));
                    curr_target += 1;
                    curr_step_count = 0;
                    curr_step_limit = first_val;

                    //cout << r << ' ' << c << endl;
                    bfs(checked, bfs_queue);
                    bool is_meet = updateStatistic(checked);
                    if (curr_target > 1 && !is_meet)
                    {
                        cout << 0;
                        return;
                    }
                }

                

                //for col
            }

            //for row
        }
        int result = INT_MAX;
        for (auto&min_vec:statistic_grid)
        {
	        for (auto&step_count:min_vec)
	        {
                if (step_count >-1)
                {
                    result = min(result, step_count);
                }
		        
	        }
        }
        if (result==INT_MAX)
        {
            cout << 0;
            return;
        }
        
        cout << result;
    }
private:
    int row_size, col_size;
    vector<vector<int>>DirectionGrid;
    vector<vector<int>>statistic_grid;
};

/*
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .

3 5
41 71 . 4 8
4 7 4 4 .
7 . . . .
 */
int main()
{
    int row_size, col_size;
    cin >> row_size >> col_size;
    vector<vector<string>>origin_str_vec(row_size, vector<string>(col_size));

    for (int r=0;r<row_size; r++)
    {
	    for (int c=0;c<col_size; c++)
	    {
            cin >> origin_str_vec[r][c];
	    }
    }
    
    vector<vector<int>>grid(row_size,vector<int>(col_size));
    for (int r=0; r<row_size; r++)
    {
	    for (int c=0;c<col_size; c++)
	    {
            if (origin_str_vec[r][c]==".")
            {
                grid[r][c] = -1;
            }
            else
            {
                grid[r][c] = stoi(origin_str_vec[r][c]);
            }
	    }
    }

    //for (auto&min_vec:grid)
    //{
    //    for (auto&str:min_vec)
    //    {
    //        cout << str << ' ';
    //    }
    //    cout << '\n';
    //}

    //string str1 = "4 . . . .";
    //string str2 = ". . . . .";
    //string str3 = "7 . . . .";
    //string str1 = "4 7 . 4 8";
    //string str2 = "4 7 4 4 .";
    //string str3 = "7 . . . .";

    //vector<string>origin_str_vec = { str1,str2,str3 };
    //vector<vector<int>>grid;
    //for (auto&oh_str:origin_str_vec)
    //{
    //    vector<int>num_vec;
    //    stringstream oh_stringstream(oh_str);
    //    string token;

    //    while (oh_stringstream>>token)
    //    {
    //        if (token==".")
    //        {
    //            num_vec.push_back(-1);
    //        }
    //        else
    //        {
    //            num_vec.push_back(stoi(token));
    //        }
    //        
    //    }
    //    grid.push_back(num_vec);
    //}


    Solution01 solu;
    solu.solve01(grid);
    //vector<vector<int>>dir_grid = solu.getDirGrid();

    //for (auto&dir_vec:dir_grid)
    //{
    //    cout << dir_vec[0] << ' ' << dir_vec[1] << endl;
    //}
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
